package gold.digger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC368 {

    public List<Integer> largestDivisibleSubset(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return new ArrayList<Integer>();
        }

        Arrays.sort(arr);
        int len = arr.length;
        int[][] dp = new int[len][2];// special two dimension dp array
        for (int i = 0; i < len; i++) {
            dp[i][0] = -1;
            dp[i][1] = 1;
        }

        int maxLength = 0, maxIndex = 0;
        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] % arr[j] == 0 && dp[i][1] < dp[j][1] + 1) {
                    dp[i][0] = j;           //update dp index
                    dp[i][1] = dp[j][1] + 1;  //update size array
                }
            }

            if (dp[i][1] > maxLength) {
                maxIndex = i;
                maxLength = dp[i][1];
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = maxIndex; i >= 0; ) {
            res.add(arr[i]);
            i = dp[i][0];
        }

        return res;
    }

    public static void main(String[] args) {
        LC368 an = new LC368();
        int[] arr = {4, 8, 10, 240};
        System.out.println(an.largestDivisibleSubset(arr));

    }
}
